package solution.s_328;

/**
 * 解题思路：
 *      首先将链表按照机构拆分成两个链表。
 *      探后将两个链表进行连接便可。
 */
public class Solution20201113 {
    public ListNode oddEvenList(ListNode head) {
        // 假如 head 为空，或者只有 1 或者 2 个元素，直接返回。
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }

        // 奇偶链表
        ListNode oddHead = new ListNode();
        ListNode evenHead = new ListNode();

        // 链表指针
        ListNode oddCurNode = oddHead;
        ListNode evenCurNode = evenHead;

        // 链表拆分
        // 标识是否是奇数
        boolean isOdd = true;
        while (head != null) {
            if (isOdd) {
                oddCurNode.next = head;
                oddCurNode = oddCurNode.next;
            } else {
                evenCurNode.next = head;
                evenCurNode = evenCurNode.next;
            }

            head = head.next;
            isOdd = !isOdd;
        }

        // 偶数链表结束位置是 null
        evenCurNode.next = null;

        // 奇数链表的结束位置是偶数链表的第一个元素，注意，此时要去掉虚拟头结点
        oddCurNode.next = evenHead.next;

        // 返回链表，去掉虚拟头结点
        return oddHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
